package com.assembler.app.sort;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Random;
import java.util.Set;

import com.assembler.app.debruij.DeBruijnGraph;

/**
 * This class provides Topological sort for Succinct De Bruijn Graph.
 * 
 * This class is a part of the lab rotation project for PhD students in January
 * 2014. School of Computing National University Singapore.
 * 
 * @author Iana Pyrogova, Abha Belorkar
 * @version 1.0.1
 */
public class TopologicalSort {
	public static void runSorting(DeBruijnGraph graph) {
		Set<String> result = graph.vertexSet();
		List<String> nodes = new ArrayList<String>();
		nodes.addAll(result);
		for (int j = 0; j < nodes.size(); j++) {
			if (graph.getAllChildrenForNode(nodes.get(j)).size() > 1) {
				//System.out.println("Start sorting for node " + nodes.get(j));
				String t = topologicalSort(graph, nodes.get(j));
//				System.out.println("Finish sorting for node " + nodes.get(j) + " item #" + j
//						+ " from " + nodes.size());
				if (t != null) {
					System.out.println(nodes.get(j) + "-" + t + "|");
					//System.out.println("(s,t) = " + "(" + nodes.get(j) + ", " + t + ")");
				}
			}
		}
		// TODO creat Map <s,t> for superbubbles

	}

	public static String topologicalSort(DeBruijnGraph graph, String jNode) {

		Queue<String> stack = new LinkedList<String>();
		List<String> seen = new LinkedList<String>();
		List<String> visited = new LinkedList<String>();
		List<String> superbubbleParentsList = new LinkedList<String>();
		superbubbleParentsList.add(jNode);
		stack.add(jNode);// Create a new S and push s into it.
		seen.add(jNode);

		while (!stack.isEmpty()) { // Repeat till |S| != 0
			String currentNode = stack.peek();
			visited.add(currentNode);
			// System.out.println("current node " + currentNode);
			if (seen.contains(currentNode)) {
				seen.remove(currentNode);
			}
			// If v does not have a child - continue
			if (graph.outDegreeOf(currentNode) == 0) {
				return null;// TODO throw to the high level loop
			} else {
				/*
				 * For every child u of v: if u = s, then continue (cycle
				 * including s ) else Make seen[u] = 1 if every parent of u is
				 * visited, then push u into S.
				 */
				List<String> children = graph.getAllChildrenForNode(currentNode);
				for (String child : children) {
					if (child.equals(jNode)) {
						return null; // TODO add label to the first circle
					} else {
						// add only unique child
//						if (isCycleBetweenChildAndAllHisParents(child, superbubbleParentsList,
//								graph, jNode)) {
//							return null; // a circle
//						}
						if (!seen.contains(child)) {
							seen.add(child);
							superbubbleParentsList.add(child);
						}
						if (isAllParentsVisited(graph, child, visited, jNode)) {
							stack.add(child);
						}
					}
				}
				if (isAllParentsVisited(graph, currentNode, visited, jNode)) {
					stack.remove(currentNode);
					// System.out.println("Element removed");
				}
//				 System.out.println("size s = "+stack.size() );
//				 System.out.println("size seen = "+seen.size() );
				if (stack.size() == 1 && seen.size() == 1) {
					String current = stack.peek();
					visited.add(current);
					seen.remove(current);
					List<String> tChildren = graph.getAllChildrenForNode(current);
					if (!tChildren.contains(jNode)) {
						return current;// Finaly findes t !
					} else
						return null;// TODO throw to the high level loop
				}
			}

		}
		return null;

	}

	// check only potential parents from current superbubble.
	private static boolean isAllParentsVisited(DeBruijnGraph graph, String child,
			List<String> visited, String jNode) {
		if (child.equals(jNode)) {
			return true;
		}
		List<String> parents = graph.getAllParentsForNode(child);
		int tmp = 0;
		for (int j = 0; j < parents.size(); j++) {
			if (visited.contains(parents.get(j))) {
				tmp++;
			}
		}
		return tmp == parents.size();
	}

	private static List<String> getParentsOnlyFromSyperbubbleForChild(String child,
			List<String> allExistingParents, DeBruijnGraph graph) {
		List<String> parentsAll = graph.getAllParentsForNode(child);
		List<String> parentsOnlyFromSyperbubble = new ArrayList<>();
		for (int j = 0; j < parentsAll.size(); j++) {
			if (allExistingParents.contains(parentsAll.get(j))) {
				parentsOnlyFromSyperbubble.add(parentsAll.get(j));
			}
		}
		return parentsOnlyFromSyperbubble;
	}

	private static boolean isCycleBetweenChildAndAllHisParents(String child,
			List<String> allExistingParents, DeBruijnGraph graph, String jNode) {
		List<String> parentsOnlyFromSyperbubble = getParentsOnlyFromSyperbubbleForChild(child,
				allExistingParents, graph);
		// System.out.println("in isCycleBetweenChildAndAllHisParents");
		for (int j = 0; j < parentsOnlyFromSyperbubble.size(); j++) {
			if (parentsOnlyFromSyperbubble.get(j).equals(jNode)) {
				// System.out.println("exist isCycleBetweenChildAndAllHisParents");
				return false;
			} else {
				List<String> grandParents = getParentsOnlyFromSyperbubbleForChild(
						parentsOnlyFromSyperbubble.get(j), allExistingParents, graph);

				if (!grandParents.contains(jNode)) {
					parentsOnlyFromSyperbubble.addAll(grandParents);
				} else {
					if (!(parentsOnlyFromSyperbubble.get(j).equals(parentsOnlyFromSyperbubble
							.get(parentsOnlyFromSyperbubble.size() - 1)))) {
						continue;
					} else {
						break;
					}
				}
			}
		}
		// System.out.println("exist isCycleBetweenChildAndAllHisParents");
		return parentsOnlyFromSyperbubble.contains(child);
	}

}
